package com.moon.homework;

import com.moon.homework.java.MultiThreadSort;
import com.moon.homework.java.SortUtils;
import org.junit.Test;

import java.time.Duration;
import java.time.LocalDateTime;
import java.util.*;

public class SortMain {
    public static void main(String[] args) {
        // 设置数组长度
        int length = 100000000;
        // 用随机数初始化数组, 数据取值范围:[-1 * length, length]
        int[] array = SortUtils.initArray(-1 * length * 10, length * 10, length);
        // int[] array = {1000, 1100, 1000, 1000, 1300};
        // length = array.length;
        // 复制两份数组对照排序
        int[] copyArray1 = new int[length];
        int[] copyArray2 = new int[length];
        System.arraycopy(array, 0, copyArray1, 0, array.length);
        System.arraycopy(array, 0, copyArray2, 0, array.length);
        System.out.println("数据个数: " + array.length);
        System.out.println("数据区间: ["+ (-1 * length * 10) + ", " + (length * 10) + "]");

        // 多线程排序
        LocalDateTime startTime = LocalDateTime.now();
        MultiThreadSort.multiThreadSort(array);
        LocalDateTime endTime = LocalDateTime.now();
        long duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("多线程排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(array));
        System.out.println("---------------------------");

        // 单线程排序
        startTime = LocalDateTime.now();
        // SortUtils.mergeSort(copyArray1);
        SortUtils.quickSort(copyArray1);
        endTime = LocalDateTime.now();
        duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("单线程快速排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(copyArray1));
        System.out.println("---------------------------");

        // 单线程排序
        startTime = LocalDateTime.now();
        SortUtils.mergeSort(copyArray2);
        endTime = LocalDateTime.now();
        duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("单线程归并排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(copyArray2));
    }

    /**
     * 五种排序算法比较
     */
    @Test
    public void compareSort(){
        // 设置数组长度
        int length = 50000;
        // 用随机数初始化数组, 数据取值范围:[-1 * length, length]
        int[] array = SortUtils.initArray(-1 * length * 10, length * 10, length);
        // 复制两份数组对照排序
        int[] copyArray1 = new int[length];
        int[] copyArray2 = new int[length];
        int[] copyArray3 = new int[length];
        int[] copyArray4 = new int[length];
        // int[] copyArray5 = new int[length];
        System.arraycopy(array, 0, copyArray1, 0, array.length);
        System.arraycopy(array, 0, copyArray2, 0, array.length);
        System.arraycopy(array, 0, copyArray3, 0, array.length);
        System.arraycopy(array, 0, copyArray4, 0, array.length);
        // System.arraycopy(array, 0, copyArray5, 0, array.length);
        System.out.println("数据个数: " + array.length);
        System.out.println("数据区间: ["+ (-1 * length * 10) + ", " + (length * 10) + "]");

        // 单线程快速排序
        LocalDateTime startTime = LocalDateTime.now();
        SortUtils.quickSort(copyArray1);
        LocalDateTime endTime = LocalDateTime.now();
        long duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("快速排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(copyArray1));
        System.out.println("---------------------------");

        // 单线程归并排序
        startTime = LocalDateTime.now();
        SortUtils.mergeSort(copyArray2);
        endTime = LocalDateTime.now();
        duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("单线程归并排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(copyArray2));
        System.out.println("---------------------------");

        // 单线程基数排序
        startTime = LocalDateTime.now();
        SortUtils.radixSort(copyArray3);
        endTime = LocalDateTime.now();
        duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("基数排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(copyArray3));
        System.out.println("---------------------------");

        // 单线程希尔排序
        startTime = LocalDateTime.now();
        SortUtils.shellSort(copyArray4);
        endTime = LocalDateTime.now();
        duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("希尔排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(copyArray4));
        System.out.println("---------------------------");

        // 单线程选择排序
        startTime = LocalDateTime.now();
        SortUtils.selectSort(array);
        endTime = LocalDateTime.now();
        duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("选择排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(array));
        System.out.println("---------------------------");
    }

    /**
     * 单独比较快速排序和基数排序
     */
    @Test
    public void compareQuickSortAndRadix(){
        // 设置数组长度
        int length = 50000000;
        // 用随机数初始化数组, 数据取值范围:[-1 * length, length]
        int[] array = SortUtils.initArray(-1 * length * 10, length * 10, length);
        // 复制两份数组对照排序
        int[] copyArray1 = new int[length];
        // int[] copyArray5 = new int[length];
        System.arraycopy(array, 0, copyArray1, 0, array.length);
        System.out.println("数据个数: " + array.length);
        System.out.println("数据区间: ["+ (-1 * length * 10) + ", " + (length * 10) + "]");

        // 单线程快速排序
        LocalDateTime startTime = LocalDateTime.now();
        SortUtils.quickSort(copyArray1);
        LocalDateTime endTime = LocalDateTime.now();
        long duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("快速排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(copyArray1));
        System.out.println("---------------------------");


        // 单线程基数排序
        startTime = LocalDateTime.now();
        SortUtils.radixSort(array);
        endTime = LocalDateTime.now();
        duration = Duration.between(startTime, endTime).toMillis();
        System.out.printf("基数排序耗时: %ss\n", duration/1000d);
        System.out.println("是否有序: " + SortUtils.isSorted(array));
        System.out.println("---------------------------");
    }

    @Test
    public void showMultiThreadSortTime(){
        List<Integer> dataCount = new ArrayList<Integer>();
        // dataCount.add(1000000);
        // dataCount.add(2000000);

        for (int i = 1; i <= 300; i++) {
            dataCount.add(1000000 * i);
        }

        LocalDateTime startTime;
        LocalDateTime endTime;

        List<String> info = new LinkedList<>();
        List<Double> multiSortTimes = new LinkedList<>();
        List<Double> quickSortTimes = new LinkedList<>();
        List<Double> mergeSortTimes = new LinkedList<>();
        List<String> multiSortTimesStr = new LinkedList<>();
        List<String> quickSortTimesStr = new LinkedList<>();
        List<String> mergeSortTimesStr = new LinkedList<>();
        List<String> lengthStr = new LinkedList<>();

        for (Integer length : dataCount) {
            int[] array = SortUtils.initArray(0, length * 7, length);

            String dataLength;
            String dataNLength;
            if (length >= 100000000) {
                dataLength = ((double)length) / 100000000 + "亿";
                dataNLength = ((double)length) / 100000000 + "\\n亿";
            } else {
                dataLength = length / 10000 + "万";
                dataNLength = length / 10000 + "\\n万";
            }

            // 复制两份数组对照排序
            int[] copyArray1 = new int[length];
            System.arraycopy(array, 0, copyArray1, 0, array.length);

            lengthStr.add("'"+dataNLength+"'");
            System.out.println("数据长度: " + length);
            System.out.println("数据区间: [0, " + (length * 7) + "]");
            // 多线程排序
            startTime = LocalDateTime.now();
            MultiThreadSort.multiThreadSort(array);
            endTime = LocalDateTime.now();
            long duration = Duration.between(startTime, endTime).toMillis();
            double multiTime = duration / 1000d;
            System.out.printf("多线程排序耗时: %ss\n", multiTime);
            System.out.println("是否有序: " + SortUtils.isSorted(array));
            System.out.println("---------------------------");
            multiSortTimes.add(multiTime);
            multiSortTimesStr.add("'" +multiTime + "s'");

            int[] copyArray2 = new int[length];
            System.arraycopy(copyArray1, 0, copyArray2, 0, array.length);
            // 单线程排序
            startTime = LocalDateTime.now();
            SortUtils.quickSort(copyArray1);
            endTime = LocalDateTime.now();
            duration = Duration.between(startTime, endTime).toMillis();
            double quickSortTime = duration / 1000d;
            System.out.printf("单线程快速排序耗时: %ss\n", quickSortTime);
            System.out.println("是否有序: " + SortUtils.isSorted(copyArray1));
            System.out.println("---------------------------");
            quickSortTimes.add(quickSortTime);
            quickSortTimesStr.add("'"+quickSortTime+"s'");

            // 单线程排序
            startTime = LocalDateTime.now();
            SortUtils.mergeSort(copyArray2);
            endTime = LocalDateTime.now();
            duration = Duration.between(startTime, endTime).toMillis();
            double mergeSortTime = duration / 1000d;
            System.out.printf("单线程归并排序耗时: %ss\n", mergeSortTime);
            System.out.println("是否有序: " + SortUtils.isSorted(copyArray2));
            mergeSortTimes.add(mergeSortTime);
            mergeSortTimesStr.add("'"+mergeSortTime+"s'");
            System.out.println("---------------------------");
            info.add("| " + dataLength + " | " + "[0, " + (length * 7) + "] | " + multiTime +"s | " + quickSortTime + "s | " + mergeSortTime + "s |");

        }

        System.out.println("| 数据量 | 数据区间 | 多线程排序 | 快速排序 | 归并排序 |");
        System.out.println("|---|---|---|---|---|");
        info.forEach(System.out::println);

        System.out.println("x="+dataCount);
        System.out.println("y="+multiSortTimes);
        System.out.println("y_quick="+quickSortTimes);
        System.out.println("y_merge="+mergeSortTimes);

        System.out.println("x_ticks_label="+lengthStr);
        System.out.println("y_ticks_label="+multiSortTimesStr);
        System.out.println("y_quick_ticks_label="+quickSortTimesStr);
        System.out.println("y_merge_ticks_label="+mergeSortTimesStr);
    }
}
